#ifndef _MUNIX_PQUEUE_H
#define	_MUNIX_PQUEUE_H
/*******************************************************************************
 ** Name: pqueue.h                                                            **
 ** Description: Priority queue implementation                                **
 **                                                                           **
 ** Open Source Initiative (OSI) Approved License                             **
 **                                                                           **
 **  Copyright (c) 2009-2010 Barry "Gian" James  <bjames@munixos.net>         **
 **  All rights reserved.                                                     **
 **                                                                           **
 **  Redistribution and use in source and binary forms, with or without       **
 **  modification, are permitted provided that the following conditions are   **
 **  met:                                                                     **
 **                                                                           **
 **  * Redistributions of source code must retain the above copyright notice, **
 **    this list of conditions and the following disclaimer.                  **
 **  * Redistributions in binary form must reproduce the above copyright      **
 **    notice, this list of conditions and the following disclaimer in the    **
 **    documentation and/or other materials provided with the distribution.   **
 **                                                                           **
 **  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS      **
 ** "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED **
 ** TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           **
 ** PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT        **
 ** HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,    **
 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED  **
 ** TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR    **
 ** PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    **
 ** LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      **
 ** NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        **
 ** SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              **
 **                                                                           **
 ******************************************************************************/
// $Id$
// $Id$

#include "common.h"

#define DEFAULT_PQUEUE_MAX     32

// This is a container class implementing a binary heap priority queue.
// Operations run in O(lg n) time.  Useful for scheduling queues, like
// those found in the bus controllers and cpu scheduler factor.

class PriorityQueue
{
 public:
            template<class CKey, class CVal>
            class QueueObj {
            public:
                QueueObj() { }
                QueueObj(CKey k, CVal v) : key(k), value(v) { }
                CKey    Key() { return key; }
                CVal    Val() { return value; }
            private:
                CKey     key;
                CVal     value;
            };

    PriorityQueue(uint8 ms = DEFAULT_PQUEUE_MAX);
    ~PriorityQueue();

   
    template<class CKey, class CVal>
    bool    Enqueue(const QueueObj<CKey,CVal> & newObj);

    template<class CKey, class CVal>
    QueueObj<CKey,CVal> & Dequeue(QueueObj<CKey, CVal> & qo);
    
    uint8   Maximum() { if (bIsHeap) return 0; else return 1; }
    //uint8   MostStarved();
  
    template<class CKey, class CVal>
    QueueObj<CKey, CVal> & ExtractMaxPriority();

    inline bool    IsOwner() { return bOwner; }
    inline void    SetOwner(bool b) { bOwner = b; }
    inline bool    IsEmpty() { return (numItems == 0); }
    inline bool    IsHeap() { return bIsHeap; }

private:
    void    BuildHeap();
    template<class CKey, class CVal>
    void    BuildHeap(QueueObj<CKey, CVal> a[], uint8  root, uint8 n);
    void    Heapify(uint8 i);
    template<class CKey, class CVal>
    void    swap(QueueObj<CKey, CVal> &, QueueObj<CKey, CVal> &);
    template<class CKey, class CVal>
    void    ArrayToHeap(QueueObj<CKey, CVal> a[], uint8 ni);
    template<class CKey, class CVal>
    void    HeapSort(QueueObj<CKey, CVal> a[], uint8 n);

    // Array index helpers
    inline uint8   Parent(uint8 i) { return (i>>1); }
    inline uint8   Left(uint8 i) { return (i<<1); }
    inline uint8   Right(uint8 i) { return ((2*i)+1); }

    const uint8  maxItems;
    uint8   numItems;
    bool    bOwner;
    bool    bIsHeap;

    template<class CKey, class CVal>
    QueueObj<CKey, CVal>  array[DEFAULT_PQUEUE_MAX];
    
};

 template<class CKey, class CVal>
void
PriorityQueue::swap(QueueObj<CKey, CVal>& o1, QueueObj<CKey, CVal>& o2)
{
    QueueObj<CKey, CVal> curr(o1);
    o1 = o2;
    o2 = curr;
}
 template<class CKey, class CVal>
void
PriorityQueue::HeapSort(QueueObj<CKey, CVal> a[], uint8 ni)
{
    for (uint8 root = ni/2 - 1; root >= 0; root--)
        BuildHeap(a,root,ni);
    for (uint8 last = ni - 1; last > 0;)
    {
        swap(a[0], a[last]);
        --last;
        BuildHeap(a,0,last);
    }
}

template<class CKey, class CVal>
void
PriorityQueue::ArrayToHeap(QueueObj<CKey, CVal> a[], uint8 ni)
{
    for (uint8 root = (ni/2)-1; root >= 0; root--)
        BuildHeap(a,root,ni);
}

template<class CKey, class CVal>
QueueObj<CKey, CVal> &
PriorityQueue::ExtractMaxPriority()
{
    QueueObj<CKey,CVal> & highest = array[0];
    array[0] = array[--numItems];
    BuildHeap(0);
    return highest;
}


void
PriorityQueue::Heapify(uint8 i)
{
    uint8 largest;
    uint8 left  = Left(i);
    uint8 right = Right(i);
    if (left <= numItems && array[left].Key() > array[i].Key())
        largest = left;
    else
        largest = i;
    if (right <= numItems && array[right].Key() > array[i].Key())
        largest = right;
    if (largest != i) {
        swap(array[i],array[largest]);
        Heapify(largest);
    }
}

void
PriorityQueue::BuildHeap()
{
    numItems = maxItems;
    for(uint8 x = maxItems>>1; x > 0; x--)
        Heapify(x);
    bIsHeap = true;
}

template<class CKey, class CVal>
void
PriorityQueue::BuildHeap(QueueObj<CKey, CVal> a[], uint8 root, uint8 n)
{
    uint8 child = 2 * root + 1;
    if (child < n) {
        uint8 right = child + 1;
        if (right < n && a[right].Key() > a[child].Key())
            child = right;
        if (a[root].Key() < a[child].Key())
        {
            swap(a[root],a[child]);
            BuildHeap(a,child,n);
        }
    }
}



PriorityQueue::PriorityQueue(uint8 ms)
: maxItems(ms)
{
    //array = new QueueObj<CKey,CVal> * [ms];

    numItems = 0;
    bOwner = true;
    bIsHeap = false;
}

PriorityQueue::~PriorityQueue()
{

}

QueueObj<CKey,CVal> &
PriorityQueue::Dequeue(QueueObj<CKey, CVal> & qo)
{
    QueueObj<CKey, CVal> & ret = array[0];
    array[0] = array[numItems];
    --numItems;
    BuildHeap();

    return ret;
}

 template<class CKey, class CVal>
bool
PriorityQueue::Enqueue(const QueueObj<CKey, CVal> & newObj)
{
    ++numItems;
    uint8 i = numItems;
    while(i > 1 && array[Parent(i)].Key() < newObj.Key())
    {
        swap(array[i], array[Parent(i)]);
        i = Parent(i);
    }
    array[i] = newObj;
    return true;
}


#if 0
// TODO
 template <class CKey, class CVal>
QueueObj<CKey, CVal> &
PriorityQueue::MostStarved()
{
    return array[0];
}
#endif


#endif	/* _MUNIX_PQUEUE_H */

